package com.zlk.algorithm.algorithm.dynamicPlan;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

// 最长有效括号
// 给你一个只包含 '(' 和 ')' 的字符串
// 找出最长有效（格式正确且连续）括号子串的长度。
// 测试链接 : https://leetcode.cn/problems/longest-valid-parentheses/
public class Code06_LongestValidParentheses {
    //   (()(            () ((())   ()()()  (()
    //   )()())
    //  ( ()() )
    //  0  2 4
    public int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();

        //dp[i] 表示当前i位置的连续的最大条件长度
        int[] dp = new int[s.length()+1];
        int max=0;
        for (int i = 1; i < chars.length; i++) {
            if(chars[i]==')'){
                int pre = i - dp[i - 1] - 1;
                //  ?         )
                //  p         i
                //    () ( ()() )
                if (pre >= 0 && chars[pre] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre - 1 >= 0 ? dp[pre - 1] : 0);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    public int longestValidParentheses2(String s) {
        char[] chars = s.toCharArray();
        //dp[i] 表示当前i位置的连续的最大条件长度
        int[] dp = new int[s.length()+1];
        int max=0;
        for (int i = 1; i < chars.length; i++) {
            if(chars[i]==')'){
                int pre = 0;
                if(chars[i-1]=='('){
                    pre = i-1;
                    dp[i] = 2+(i-2>0?dp[pre-1]:0);
                }else{
                    pre = i - dp[i - 1] - 1;
                    //  ?         )
                    //  p         i
                    //    () ( ()() )
                    if (pre >= 0 && chars[pre] == '(') {
                        dp[i] = dp[i - 1] + 2 + (pre - 1 >= 0 ? dp[pre - 1] : 0);
                    }
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }


    public static void main(String[] args) {
        longestValidParentheses3("())((())");
    }

    /**
     * 利用栈  暂时理解不了
     * @param s
     * @return
     */
    public static int longestValidParentheses3(String s) {
        int maxans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);

        // (()))
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }



}
